Pattern search is a simple yet powerful machine vision tool. Given a template pattern and an image, its objective is to find all instances of the patterns in the image. It involves two steps, a search step and a match step. The search step places the pattern at all valid poses (locations, rotation angles), and scales of the image being searched. The match step determines the goodness of the match between the pattern at a given pose and scale and the subset of the image corresponding to the pose and scale. The normalized correlation method (Ballard D H and Brown C M, “Computer Vision”, Prentice Hall 1982, pp. 68–70) of fixed rotation and scale has been widely used as the matching method in many machine vision applications. The match score of normalized correlation is largely independent of linear variations in object shading caused by reflectivity or illumination variations. However, pattern search based on a normalized correlation method is inherently computationally demanding since it requires operations between two (pattern and image) two-dimensional regions on all valid image locations. Even with the state-of-the-art computers, it is still difficult to achieve real-time performance when the image or pattern size is large. Furthermore, it does not work well when the pattern being searched is subject to rotation and/or size/aspect ratio variations. The match score could drop significantly even if only a few degrees of rotation or a few percent of size change occurs. One prior art approach to rotation and scale invariance is to rotate and scale the pattern template and try all possible scale and rotation combinations. However, this imposes an even greater computational demand that cannot be accomplished using normalized correlation.
Another prior art approach is the use of a geometric pattern matching method such as PatMax introduced by Cognex (Silver B, “Geometric Pattern Matching for General-Purpose Inspection in Industrial Machine Vision”, Intelligent Vision '99 Conference, Jun. 28–29, 1999). This approach uses geometric information in place of pixel grid-based correlation. For example, it interprets a square as four line segments and a football as two arcs. It extracts key geometric features within an object image such as boundary encoding and measures characteristics such as shape, dimensions, angle, arcs, and shading. It then corresponds the spatial relationships between the key features of the pattern template and the new image. However, this prior art approach requires high edge contrast and low noise between patterns and background to reliably extract the key geometric features. It fails when edges of a pattern are not well defined. This is the inherent problem when using the geometric approach in place of any pixel grid based approach.
A rotation and scale invariant pattern matching method was disclosed (Shih-Jong J. Lee et. al., “A Rotation and Scale Invariant Pattern Matching Method”, U.S. patent application Ser. No. 09/895,150 filed Apr. 10, 2002) that generates a polar coordinate representation of the pattern template image thereby allows for fast linear search of scale along the radius axis and rotation along the angular axis. Fast search can be achieved by projecting image intensities into the radius axis for scale search and projecting image intensities into the angular axis for rotation angle search. However, this method requires that the polar coordinate transformation be performed on each image region where the rotation and scale invariant pattern matching method is applied. This could be time consuming if image regions centered at all positions of an image are subjected to the search. It is desirable to have a fast initial invariant search method that quickly identifies a reduced set of image positions where the finer rotation and scale invariant pattern matching method can be applied.
Furthermore, the speed of prior art invariant search method depends on the range of rotation angles that need to be searched. It is time consuming when the rotation angle search range is large. It is desirable to have an invariant search method that does not depend on the rotation angle search range.
A fast regular shaped pattern search method was disclosed (Shih-Jong J. Lee et. al., “Fast Regular Shaped Pattern Searching”, U.S. patent application Ser. No. 10/255,016 filed on Sep. 24, 2002) that performs fast pattern matching with flexible projection kernels to construct regular-shaped patterns using an accumulation method. This invention generates rotation and scale invariant profiles using the fast regular shaped pattern construction method. The rotation and scale invariant profiles are then used to perform fast invariant search for initial detection of the match candidates.